#include <stdlib.h>
#include <time.h>
#include <stdio.h>

#define ARRAY_SIZE 10
#define NUMBER_RANGE 1000
#define NUMBER_DIGITS 3
#define RADIX 10

int find_digit(int elem,int offset){
	int digit = elem;
	int j=0;
	for(j=1;j<offset;j++){
		digit /=10; 
	}
	digit%=10;
	return digit;
}

void sort_per_digit(int arr[],int len,int ret[],int offset) {

    int count[RADIX];
    int i=0;
    for(i=0;i<RADIX;i++) {
		count[i]=0;	
    }
	
    for(i=1;i<=len;i++) {
		count[find_digit(arr[i],offset)]++;
    }
	
    for(i=1;i<RADIX;i++) {
		count[i]+=count[i-1];	
    }
    for(i=len;i>0;i--) {
		ret[count[find_digit(arr[i],offset)]]=arr[i];
		count[find_digit(arr[i],offset)]--;
    }
}

void radix_sort(int arr[],int temp[],int len,int digits){
	int i=0;
	int j=len;
	for(i=1;i<=digits;i++){
		sort_per_digit(arr,len,temp,i);
		while(j-->1){
			arr[j]=temp[j];
		}
	}
}
int main(){
    int i = 0;
    int arr[ARRAY_SIZE+1];
    int ret[ARRAY_SIZE+1];

    srand((unsigned)time(NULL));
    for(i=1;i<=ARRAY_SIZE;i++){
        arr[i] = rand()%NUMBER_RANGE;
    }

    printf("sort array  [");
    for(i=1;i<=ARRAY_SIZE;i++){
        printf("%d",arr[i]);
        if(i<ARRAY_SIZE){
            printf(",");
        }
    }
    printf("] \n");
    radix_sort(arr,ret,ARRAY_SIZE,NUMBER_DIGITS);

    printf("sort result [");
    for(i=1;i<=ARRAY_SIZE;i++){
        printf("%d",ret[i]);
        if(i<ARRAY_SIZE){
            printf(",");
        }
    }
    printf("] \n");

    return 0;
}

